User blog:Upquark11111/Ordinals in the Calculus of Constructions
This is somewhat of a follow-up to my blog post explaining Loader's number, and also to present some new techniques for constructions of fast-growing functions in typed lambda calculi. I left an open space in the appendix to update later, explaining how to construct fast-growing functions in λPω. However, when I found a way to reach past \varepsilon _0 , I realized that explaining it would take too much space. The subject of encoding ordinals in λPω deserves a blog post of its own. So, in this post I'm going to be defining an encoding of ordinals in the Calculus of Constructions, and further use that to construct the Hardy hierarchy. I'm going to assume you understand the basics of currying, typed lambda calculus, and the Calculus of Constructions. If you're not familiar with these, you can check out my blog post on Loader's number for a brief introduction. Some google-fu can be useful if you want to read up further into it. Naturals in λPω If you already have a solid grasp of the Church encoding in polymorphic lambda calculi, you can skip this section. Otherwise, here is the definition of natural numbers in polymorphic lambda calculi on the lambda cube: \mathrm{nat} = \Pi A:\ast .(A\rightarrow A)\rightarrow A\rightarrow A . This is a polymorphic type, meaning we can switch out that A for any other type we would need it to be. Essentially, this type encodes natural numbers as function iterators. Natural numbers take in a function and return another function. The output function is exactly the input function iterated n times, where n is the number encoded by the term. A function from what to what, though? That's what the polymorphism is for. It can be a function from any type to that same type. For example, we can even let A be the natural numbers, so we can iterate functions on naturals. In this encoding, we would make the following definitions: 0=\lambda A:\ast .\lambda f:A\rightarrow A.\lambda x:A.x , \mathrm{succ}=\lambda n:\mathrm{nat}.\lambda A:\ast .\lambda f:A\rightarrow A.\lambda x:A.f\ (n\ A\ f\ x) . So, 0 iterates the given function 0 times, and succ adds another iteration to a natural number, thereby incrementing it. Arithmetic operators Let's define some arithmetic operations now. First obvious one is addition. We could just define that to be an iteration of succ on a number. So, \mathrm{add}=\lambda m:\mathrm{nat}.\lambda n:\mathrm{nat}.n\ \mathrm{nat}\ \mathrm{succ}\ m . The first parameter here is nat, because we want to iterate a function from nat to nat. That is the next parameter, succ. The last parameter is the input for our function iterate, m. So, this amounts to evaluating \mathrm{succ}^n (m) . Next, let's look at multiplication. \mathrm{mul}=\lambda m:\mathrm{nat}.\lambda n:\mathrm{nat}.n\ \mathrm{nat}\ (\mathrm{add}\ m)\ 0 We use the same technique as with addition. We're iterating the function k\mapsto m+k , n times. That amounts to adding m to something n times. That something is 0. We can keep continuing along this route to define exponentiation, tetration, pentation, etc. If you're clever, you can diagonalize over this by defining a function that takes in an operator and returning the next level of operators. You could then iterate that to create a hyperoperator function. Limitations Hyperoperators are pretty weak by googological standards. At best, this method can only be used to reach growth rates of f_{\varepsilon _0} . If we want to go further, we would need to find a way to extend our natural number encoding to include ordinals. Then, maybe we could go further. Ordinals in λPω How do we extend the Church encoding to encode transfinite ordinals? Well, let's look a bit closer at the Church encoding. One way to think of it is as a function iterator. Another way is to look at it as a limited implementation of recursion. It's sort of like a (rather monotonous) game where you have a starting value x and a Church numeral n. You decrement n until you reach 0, and each time you decrement you do something to x. Eventually, you'll end up doing that thing n times. Now, here's what we can do to encode ordinals in lambda calculus: you have an ordinal α and a starting value z. While α is a successor ordinal, decrement it and do action s to the value z. However, if α is a limit ordinal, you play this game with the ordinal αn and do action l to the end result of that game. Here, what n is depends on what the action l is. How do we add this to our definition then? In the original Church encoding, it takes the action s and the starting value z as input. So, we need only to add the action l as a possible input to extend our definition to include ordinals. Remember how l indexes the fundamental sequence of the ordinal and does something to it? I say it that way because we want the action l to be very flexible. So, l should be able to have some kind of access to the fundamental sequence of α. Maybe, we could have a function that enumerates the fundamental sequence of α, but each element αn is replaced with the end result of the game using αn. So, the function l should have the type (\mathrm{nat}\rightarrow A)\rightarrow A The game basically captures what's going on when you make the application (α A l s z), and is a form of transfinite recursion. As transfinite recursion, l acts as the limit step and s acts as the successor step. z is the base case. The definition With that, let's get into the definitions. \mathrm{ord}=\Pi A:\ast .((\mathrm{nat}\rightarrow A)\rightarrow A)\rightarrow (A\rightarrow A)\rightarrow A\rightarrow A 0=\lambda A:\ast .\lambda l:(\mathrm{nat}\rightarrow A)\rightarrow A.\lambda s:A\rightarrow A.\lambda z:A.z \mathrm{succ}=\lambda \alpha :\mathrm{ord}.\lambda A:\ast .\lambda l:(\mathrm{nat}\rightarrow A)\rightarrow A.\lambda s:A\rightarrow A.\lambda z:A.s\ (\alpha\ A\ l\ s\ z) \mathrm{lim}=\lambda f:\mathrm{nat}\rightarrow\mathrm{ord}.\lambda A:\ast .\lambda l:(\mathrm{nat}\rightarrow A)\rightarrow A.\lambda s:A\rightarrow A.\lambda z:A.l\ (\lambda n:\mathrm{nat}.(f\ n)\ A\ l\ s\ z) In our new encoding, 0 and succ appear to be basically the same. But now we introduce a new function, lim. lim is the function that generates limit ordinals. It takes in a function f that maps natural numbers to ordinals, and returns the limit of that function. f is used as the fundamental sequence of the resulting ordinal. Notice how, in the output ordinal, we see that applying the ordinal results in the action of l upon the enumeration of applications of ordinals (f n) in the fundamental sequence. If you want, you can define l to index that enumeration at a certain n and perform an action on that value. If you try applying ordinals, you might find that it satisfies the rules of the game described earlier. Ordinal arithmetic Now let's define some ordinal arithmetic. Let's start with addition. First, let's think about what we want to do on the successor step and the limit step. When adding two ordinals α and β, we want to keep decrementing β while incrementing α. However, when β becomes a limit ordinal, what do we do? Then \alpha + \beta should be equal to the limit of the function n\mapsto \alpha + \beta n . Based on these rules, we should set s=succ and l=lim. Hence, our addition function must be \mathrm{add}=\lambda \alpha :\mathrm{ord}.\lambda \beta :\mathrm{ord}.\beta\ \mathrm{ord}\ \mathrm{lim}\ \mathrm{succ}\ \alpha . We can apply similar principles to define multiplication as \mathrm{mul}=\lambda \alpha :\mathrm{ord}.\lambda \beta :\mathrm{ord}.\beta\ \mathrm{ord}\ \mathrm{lim}\ (\mathrm{add}\ \alpha)\ 0 . As will be useful soon, we can define the function \alpha\mapsto\omega ^{\alpha} in λPω as: \mathrm{exp}_\omega =\lambda \alpha :\mathrm{ord}.\alpha\ \mathrm{ord}\ \mathrm{lim}\ (\mathrm{mul}\ \omega)\ 1 , where \omega =\mathrm{lim}\ (\lambda n:\mathrm{nat}.n\ \mathrm{ord}\ \mathrm{succ}\ 0) . The Hardy hierarchy in λPω If you've ever tried expanding out and evaluating certain values of the Hardy hierarchy, you might notice that the process is very similar to the ordinal descent game I described earlier. Well, that's because it's the exact same process. The starting value z is just the function n\mapsto n , and the function s just represents the step H_{\alpha +1}(n)=H_{\alpha}(n+1) . The limit step, l, should capture H_{\alpha}(n)=H_{\alpha n}(n) . So, the implementation of the Hardy hierarchy using our encoding of ordinals is very natural. Basically, what we're going to do is we're going to construct a function that takes an ordinal α and returns a function on the Hardy hierarchy. To do this, we perform an application of α on certain functions such that the end result of the application would be the desired result. First, we set our type A to be \mathrm{nat}\rightarrow\mathrm{nat} . So, our z is just the identity function: \lambda n:\mathrm{nat}.n . Next is s, which takes in a hierarchy function f and returns the next function in the Hardy hierarchy. That's pretty trivial: \lambda f:\mathrm{nat}\rightarrow\mathrm{nat}.\lambda m:\mathrm{nat}.f\ (\mathrm{succ}\ m) . And finally, l. l takes in an enumeration of applications on the fundamental sequence of the ordinal. Remember that the results of those applications are functions on the Hardy hierarchy. So the enumeration q should be the function n\mapsto H_{\alpha n} . The lambda function \lambda m:\mathrm{nat}.q\ m\ m is just the function m\mapsto H_{\alpha m}(m) , which is what we want l to return. So, we have that l is \lambda q:\mathrm{nat}\rightarrow\mathrm{nat}\rightarrow\mathrm{nat}.\lambda m:\mathrm{nat}.q\ m\ m . Now that we have all the ingredients, we just apply any ordinal to these parameters to get the Hardy hierarchy function whose index is that given ordinal. Finally, our Hardy hierarchy function in lambda calculus is H=\lambda \alpha:\mathrm{ord}.\alpha\ (\mathrm{nat}\rightarrow\mathrm{nat})\ (\lambda q:\mathrm{nat}\rightarrow\mathrm{nat}\rightarrow\mathrm{nat}.\lambda m:\mathrm{nat}.q\ m\ m)\ (\lambda f:\mathrm{nat}\rightarrow\mathrm{nat}.\lambda m:\mathrm{nat}.f\ (\mathrm{succ}\ m))\ (\lambda m:\mathrm{nat}.m) An example usage of this lambda function would be (H\ \varepsilon _0\ 10) , which would be H_{\varepsilon _0}(10) . The Veblen hierarchy So now the question remains: how big can our ordinals get? We can very easily reach \varepsilon _0 : \varepsilon _0 = \mathrm{lim}\ (\lambda n:\mathrm{nat}.n\ \mathrm{ord}\ \mathrm{exp}_{\omega}\ (\mathrm{succ}\ 0)) . Furthermore, we can reach \varepsilon _1 by replacing that last 0 with \varepsilon _0 . In fact, we can diagonalize over this, resulting in the following function: \varepsilon = \lambda \alpha : \mathrm{ord} . ( \mathrm{succ}\ \alpha )\ \mathrm{ord}\ \mathrm{lim}\ (\lambda \beta : \mathrm{ord} . \mathrm{lim}\ (\lambda n: \mathrm{nat} . n\ \mathrm{ord}\ \mathrm{exp} _{ \omega }\ ( \mathrm{succ}\ \beta )))\ 0 . Notice how if you replace the \mathrm{exp}_{\omega} in the above expression with any Veblen function f, the expression would enumerate the fixed points of f. For example, replacing \mathrm{exp}_{\omega} with \varepsilon would enumerate the zeta ordinals. We can go a step further and diagonalize over this process to obtain a lambda expression for the two-argument Veblen function, which I will leave as an exercise to the reader. I'd imagine that this same technique can be used to extend our reach further, perhaps all the way up to \psi (\Omega ^{\Omega ^{\Omega}}) . Further developments The next obvious step would be to define ordinal collapsing functions in the language of λPω. Of course, our current definitions would not be able to do this, since the ordinal encoding I defined above can only be used to construct countable ordinals. A possible extension could be to redefine ordinals as \mathrm{ord}=\Pi A:\ast .(A\rightarrow A\rightarrow A)\rightarrow A\rightarrow ((\mathrm{nat}\rightarrow A)\rightarrow A)\rightarrow (A\rightarrow A)\rightarrow A\rightarrow A . In this possible extension, the parameter of type A\rightarrow A\rightarrow A would accept the ordinal collapsing function, and the next parameter whose type is A would be used to contain the parameter of the most recent application of the ordinal collapsing function. This would be needed to evaluate the pseudo-fundamental sequence of uncountable ordinals. This system could probably express ordinals up until \psi (\psi _I (0)) . From there, we could extend the system to reflect Rathjen's ordinal collapsing functions, and after that another extension to even reach up to \psi (\varepsilon _{K+1}) . The ultimate limit of the ordinals λPω could construct would be its proof-theoretic ordinal, since its very intuitionistic nature means that it can only prove an ordinal is recursive if it can construct the ordinal. It has been shown that λPω is at least as strong as higher order arithmetic, so it's quite likely that we'll never reach the growth rate of Loader's program without using similar techniques or uncomputable functions. Category:Blog posts